# define _CRT_SECURE_NO_WARNINGS 1
#include "BinaryTree.h"

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL ");
		return;
	}
	else
	{
		printf("%c ", root->data);
		PrevOrder(root->left);
		PrevOrder(root->right);
	}
}




void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL ");
		return;
	}
	else
	{
		InOrder(root->left);
		printf("%c ", root->data);
		InOrder(root->right);
	}
}




void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL ");
		return;
	}
	else
	{
		PostOrder(root->left);
		PostOrder(root->right);
		printf("%c ", root->data);
	}
}




//int TreeSize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return;
//	}
//	static int size = 0;
//	++size;
//	TreeSize(root->left);
//	TreeSize(root->right);
//	return size;
//}
//void TreeSize(BTNode* root, int* psize)
//{
//	if (NULL == root)
//	{
//		return;
//	}
//	(*(psize))++;
//	TreeSize(root->left, psize);
//	TreeSize(root->right, psize);
//}
int TreeSize(BTNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

//int TreeLeafSize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return;
//	}
//	else if(root->left == NULL && root->right == NULL)
//	{
//		return 1;
//	}
//	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
//}




int MaxDepth(BTNode* root)
{
	if (!root)
	{
		return 0;
	}
	int leftdeep = MaxDepth(root->left);
	int rightdeep = MaxDepth(root->right);
	return leftdeep > rightdeep ? leftdeep + 1 : rightdeep + 1;
}

#if 0
bool IsBalanced(BTNode* root)
{

}
#endif




BTNode* PostFirst(BTNode* root)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return root;
	}
	BTNode* left = PostFirst(root->left);
	BTNode* right = PostFirst(root->right);
	if (left)
		return left;
	else
		return right;
}




BTNode* PrevLast(BTNode* root)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return root;
	}
	BTNode* right = PrevLast(root->right);
	BTNode* left = PrevLast(root->left);
	if (right)
		return right;
	else
		return left;
}




//void ExchangeChild(BTNode* root)
//{
//	if (NULL == root)
//	{
//		return;
//	}
//	if()
//}